The invention generally relates to secure network communication systems. The invention relates more specifically to a method and apparatus for distributing and updating group controllers or multicast service agents over a wide area network based on a tree structure.
The proliferation of network computing has shaped how society conducts business and personal communication. As reliance on computer networks grows, the flow of information between computers continues to increase in dramatic fashion. Accompanying this increased flow of information is a proportionate concern for network security. Commercial users, who regularly conduct business involving the exchange of confidential or company proprietary information over their computer networks, demand that such information is secure against interception by an unauthorized party or to intentional corruption. In addition, with the acceptance of electronic commerce over the global Internet, all users recognize the critical role cryptographic systems play in maintaining the integrity of network communication.
Cryptography is the art and science of keeping messages secure. A message is information or data that is arranged or formatted in a particular way. In general, a message, sometimes referred to as xe2x80x9cplaintextxe2x80x9d or xe2x80x9ccleartext,xe2x80x9d is encrypted or transformed using a cipher to create xe2x80x9cciphertext,xe2x80x9d which disguises the message in such a way as to hide its substance. In the context of cryptography, a cipher is a mathematical function that can be computed by a data processor. Once received by the intended recipient, the ciphertext is decrypted to convert the ciphertext back into plaintext. Ideally, ciphertext sufficiently disguises a message in such a way that even if the ciphertext is obtained by an unintended recipient, the substance of the message cannot be discerned from the ciphertext.
Many different encryption/decryption approaches for protecting information exist. In general, the selection of an encryption/decryption scheme depends upon the considerations such as the types of communications to be made more secure, the particular parameters of the network environment in which the security is to be implemented, and desired level of security. An important consideration is the particular system on which a security scheme is to be implemented since the level of security often has a direct effect on system resources.
For example, for small applications that require a relatively low level of security, a traditional restricted algorithm approach may be appropriate. With a restricted algorithm approach, a group of participants agree to use a specific, predetermined algorithm to encrypt and decrypt messages exchanged among the participants. Because the algorithm is maintained in secret, a relatively simple algorithm may be used. However, in the event that the secrecy of the algorithm is compromised, the algorithm must be changed to preserve secure communication among the participants. Scalability, under this approach, is an issue. As the number of participants increases, keeping the algorithm secret and updating it when compromises occur place an undue strain on network resources. In addition, standard algorithms cannot be used since each group of participants must have a unique algorithm.
To address the shortcomings of traditional restricted algorithm approaches, many contemporary cryptography approaches use a key-based algorithm. Generally two types of key-based algorithms exist: (1) symmetric algorithms and (2) asymmetric algorithms, of which one example is a public key algorithm. As a practical matter, a key forms one of the inputs to a mathematical function that is used by a processor or computer to generate a ciphertext.
Public key algorithms are designed so that the key used for encryption is different than the key used for decryption. These algorithms are premised on the fact that the decryption key cannot be determined from the encryption key, at least not in any reasonable amount of time with practical computing resources. Typically, the encryption key (public key) is made public so that anyone, including an eavesdropper, can use the public key to encrypt a message. However, only a specific participant in possession of the decryption key (private key) can decrypt the message.
Public key algorithms, however, often are not employed as a mechanism to encrypt messages, largely because such algorithms consume an inordinate amount of system resources and time to encrypt entire messages. Further, public key encryption systems are vulnerable to chosen-plaintext attacks, particularly when there are relatively few possible encrypted messages.
As a result, a public key cryptosystem generally is utilized to establish a secure data communication channel through key exchanges among the participants. Two or more parties, who wish to communicate over a secure channel, exchange or make available to each other public (or non-secure) key values. Each party uses the other party""s public key value to privately and securely compute a private key, using an agreed-upon algorithm. The parties then use their derived private keys in a separate encryption algorithm to encrypt messages passed over the data communication channel. Conventionally, these private keys are valid only on a per communication session basis, and thus, are referred to as session keys. These session keys can be used to encrypt/decrypt a specified number of messages or for a specified period of time.
A typical scenario involves participants A and B, in which user A is considered a publisher of a message to a subscriber, user B. The public key algorithm used to establish a secure channel between publisher, A, and subscriber, B, is as follows:
1. B provides a public key, B, to A.
2. A generates a random session key SK, encrypts it using public key B and sends it to B.
3. B decrypts the message using private key, b (to recover the session key SK).
4. Both A and B use the session key SK to encrypt their communications with each other; after the communication session, A and B discard SK.
The above approach provides the added security of destroying the session key at the end of a session, thereby, providing greater protection against eavesdroppers.
Once a multicast group is established, management of the sessions keys due to membership changes poses a number of problems. Forward secrecy, which arises when a member node leaves the multicast group and may still possess the capability to decipher future messages exchanged among the group, becomes a concern. In addition, in the case where a new member node enters the multicast group, the new member should not be permitted to decrypt the past messages of the multicast group. Another consideration involves making session key updates when a xe2x80x9cjoinxe2x80x9d or xe2x80x9cleavexe2x80x9d occurs; updates must be rapid to prevent undue system delay. This issue relates to how well the network scales to accommodate additional users.
Another conventional technique used to establish secure communication employs a trusted third party authentication mechanism, such as a certificate authority (xe2x80x9cCAxe2x80x9d) or key distribution center (xe2x80x9cKDCxe2x80x9d) to regulate the exchange of keys. FIG. 9 is a block diagram of a system that uses a single central group controller (GC) 901 that has responsibility for distributing, creating, and updating session keys to members of the multicast group (users A-H). The eight users, A-H, communicate with group controller 901 via separate point-to-point connections 903 to obtain a dynamic group session key. The channels 903 can be made secure by using a standard Diffie-Hellman key exchange protocol.
The group controller preferably comes to a shared Group Session key using a binary tree approach. The KDC or CA carries out a third party authentication. The keys can be sent in a multicast or broadcast messages or overlapping broadcast or multicast messages or many point to point messages. Diffie-Hellman is not required to secure communications with the group controller; the binary tree approach provides it. Ideally, only one message from the group controller is needed.
Alternatively, Diffie-Hellman is used to do a point to point communication with the CA or KDC, and the CA or KDC can give out a group session key without using the binary tree approach. All nodes get the same session key using Nxe2x88x921 point to point messages. These two approaches are orthogonal and can be combined for optimization.
To set up the secured channel among the nodes, Nxe2x88x921 messages are exchanged, wherein N is the number of nodes. Although this is relatively low overhead in terms of messages exchanged, a major drawback is that the centralized group controller 901 represents a single point of failure, and therefore the system lacks fault tolerance. If the group controller 901 is down, no secure communication can exist among the multicast group of users A-H. Such a prospect is unacceptable, especially in mission critical systems.
Another drawback is that the group controller 901 is a potential bottleneck in the network when a binary tree algorithm is used, and the KDC or CA are potential bottlenecks when other mechanisms are used. For instance, if multiple nodes request to join the multicast group, the controller 901 may not be able to process all such requests in a timely manner. This problem may be acute if the multicast group is over a wide area network (WAN). Further, a system dependent upon a group controller 901 is not easily enlarged or scaled, due, in part, to physical hardware constraints.
A binary tree approach is disclosed in co-pending application Ser. No. 09/407,785, entitled xe2x80x9cMETHOD AND APPARATUS FOR CREATING A SECURE COMMUNICATION CHANNEL AMONG MULTIPLE PROXY MULTICAST SERVICE NODES,xe2x80x9d filed Sep. 29, 1999, and naming as inventors Sunil K. Srivastava, Jonathan Trostle, Raymond Bell, and Ramprasad Golla, the entire disclosure of which is hereby incorporated by reference as if fully set forth herein. The binary tree approach described therein makes it possible to scale a secure communication system to large multicast groups, with less overhead involved in transmission of new group session keys when members join in a multicast group. Advantageously, each affected member does only log2N decryption operations; further, when a member joins or leaves, the central group controller, which acts as a group membership coordinator, sends only a subset of keys to existing group members on an affected tree branch. All keys that are affected can be sent, ideally, in one multicast or broadcast message, and only keys that correspond to a particular node will be decrypted by that node.
Further, in this approach each node member only holds log2N keys and a group session key. For each join, a new member gets log2N keys, where the first key is unique to a node. It is like a private key because only the node member and a CA or KDC can know it. When a node sends a join request to a Group Manager, after Authentication and Validation, a signed and encrypted payload is sent to the joining member. The second key is encrypted with the first key and the third key is encrypted with the second key and so on, until the Group Key is encrypted with the last key. Only one key out of log2N keys are unique to a node and the rest are shared with other node members. The other keys are shared with other node members and are obtained from intermediate nodes of a binary tree, in which leaf nodes represent the node members having private keys.
The Group Manager can send the new Group Key and the new affected shared keys in one broadcast message, the size of which is 2 log2Nxe2x88x921 keys. As an optimization, it can send a broadcast message saying that it should just hash forward keys and Group keys based on an agreed hashing process. Or it can send one broadcast message with 2 log2N keys, or send 2 log2N key messages in point to point messages, each message containing one key. For a leave operation, similar key update messages are sent.
One issue with this approach, however, is that the central group controller presents a single point of failure. The KDC and CA also present a single point of failure in approaches that do not use a binary tree mechanism. An approach for avoiding a single point of failure is presented in the above-referenced co-pending application, and also in co-pending application Ser. No. NUMBER, entitled xe2x80x9cMETHOD AND APPARATUS FOR DISTRIBUTING AND UPDATING PRIVATE KEYS OF MULTICAST GROUP MANAGERS USING DIRECTORY REPLICATION,xe2x80x9d filed concurrently herewith, and naming as inventors Sunil K. Srivastava, Jonathan Trostle, Raymond Bell, and Ramprasad Golla, the entire disclosure of which is hereby incorporated by reference as if fully set forth herein.
The approach of the first application referenced above is well suited to distribution over a LAN, and the approach of the second application referenced above is well suited for use over a WAN. Accordingly, there is a clear need for improved approaches to key exchange that eliminate a single point of failure, especially among broadcast or multicast group members that operate over a WAN.
There is also a need for an approach for providing a secure communication channel among a group controller, KDC, or CA so that the group controller, KDC or CA may be distributed. Since the group controller, KDC, and CA normally are essential for establishing any secure channel, this need presents a circular or xe2x80x9cchicken and eggxe2x80x9d type of paradox.
In particular, there is an acute need for an improved approach to distribution that enhances scalability and fault tolerance of group managers over a WAN. There is also a need for improved approaches for key updating in this context.
There is a specific need for improved approaches for key distribution and updating that can eliminate the single point of failure by making group managers accessible over a WAN.
The foregoing needs, and other needs and objects that will become apparent from the following description, are fulfilled by the present invention, which comprises, in one aspect, an approach for establishing secure multicast communication among multiple multicast proxy service nodes of domains of a replicated directory service that spans a wide area network. In this context, xe2x80x9cmulticast proxy service nodexe2x80x9d refers to a Multicast Service Agent, Multicast KDC, and/or Group Controller. The domains are logically organized in the form of a first binary tree and each domain stores a logical sub-tree that organizes the multicast proxy service nodes. Each domain also comprises a group manager at the root node of the sub-tree, a key distribution center, multicast service agent, and directory service agent. Multicast proxy service nodes each store a group session key and a private key.
Replication of the directory accomplishes distribution of keys. Specifically, the MSAs form a group among themselves using the directory replication and distribute keys.
The binary tree structure may be exploited by establishing a second binary tree having real nodes that are MSAs as part of the binary tree of group of nodes for Publishers and Subscribers. The intermediate nodes of the second binary tree are MSAs that form a xe2x80x9cback channelxe2x80x9d group with other MSAs for secure communications, but with other real subscribers and publishing nodes, they form a different group and act like a local root node for the sub-tree.
A Multicast group member joins or leaves the group by publishing a message. The local key distribution center and multicast service agent obtains its own identifier from the Binary tree for a Publisher Specific Group. A secure channel is established with other MSA nodes in the Binary tree for the Publisher Specific Group. All keys of the binary tree branch that contains the joining or leaving node are updated, an updated group session key and a new private key are received.
Intermediate nodes of a binary tree represent actual multicast group members. This arrangement more naturally accommodates superimposition of multicast routing trees, reliable multicasting transport trees, hierarchical cache chaining structures, and directory trees. Using the intermediate nodes, the number of group members and keys is 2N+1xe2x88x921, and each group member stores log2n keys, where n defines the level in a tree, ranging from 0 to N, and N is the number of nodes in the tree. Under this approach, there is flexibility in implementation with regard to joining and leaving the multicast group. The number of keys affected is essentially 2log2Nxe2x88x922log2n. The intermediate node behaves as a group controller for its branch by changing the keys of the affected nodes within its branch. This reduces the workload on the group controller. As a second option, the intermediate node requests a new session key from the group controller or requests permission to create a new session key.
In the case where the group controller creates a new group session key, the group controller encrypts the new session key with the private key of the intermediate node. However, if the group session key results from a member leaving the multicast group, the intermediate node changes its key(s) since such keys were known by the leaving node. To do so, the intermediate node has a separate secured private channel with the group controller. Using this private channel, the intermediate node sends the group controller its updated keys. Alternatively, the intermediate node (which is acting as a sub-group controller) decrypts the group session key from the group controller and then encrypts the group session key with the newly created keys associated with the affected nodes.
Thus, in the approach of the invention, the Multicast GC""s, MKDC, MSA nodes form a group among themselves and use directory replication to distribute group session keys and sub keys for the ID-based Binary Tree. A first binary tree may be used for secure back channel communication; other methods also may be used to establish the secure back channel. In the approach of this invention, a second tree comprises many real nodes in that are also part of the first tree, and the intermediate nodes in the second tree act like a local group controller to spread other group controller nodes over a WAN. An advantage of this approach in which intermediate nodes act as a local GC is that the tree keys affected are local and the only global keys affected are the local GC""s private key and the group session key. The local GC can change its private key and update all GCs using the private channel. The group session key can be also be changed and other GCs can be made aware of the change. Or, a xe2x80x9cback channelxe2x80x9d can be used to request the root GC to update the private session group key.